package array.findKthLargest;
/**
 * @Date 2020/04/10
 * @author 王光浩
 * @Thinking 排序后获取第K个数，快速排序，分而治之。
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（n）
 */
public class MyMethodone {
	 public int findKthLargest(int[] nums, int k) {
		 if(nums.length==0)return -1;
		 helper(0,nums.length-1,nums);
		 return nums[nums.length-k];
	 }
	 private void helper(int left,int right,int[] nums) {
		 if(left>=right)return;
		 int l=left;
		 int r=right;
		 int tem=nums[l];  //基数
		 while(l<r) {
			 while(r>l && nums[r]>=tem)r--;
			 nums[l]=nums[r];
			 while(r>l && nums[l]<tem)l++;
			 nums[r]=nums[l];
		 }
		 nums[l]=tem;
		 helper(left,l-1,nums);
		 helper(l+1,right,nums);
	 }
}
